<?php
/**
 *  User：LRZ
 *  Date：2020/2/20
 *  Time：15:48
 */

/**
 *  367.有效的完全平方数
 *
 *  标签：数学、二分查找
 *
 *  给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
 *  说明：不要使用任何内置的库函数，如  sqrt。
 *
 *  示例 1：
 *      输入：16
 *      输出：True
 *
 *  示例 2：
 *      输入：14
 *      输出：False
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/valid-perfect-square
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$num = 4;
$res = isPerfectSquare($num);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function isPerfectSquare($num)
{
    if ($num < 2) {
        return true;
    }
    $left  = 0;
    $right = (int)($num / 2);

    while ($left <= $right) {
        $mid  = (int)($left + ($right - $left) / 2);
        $sqrt = $mid * $mid;
        if ($sqrt === $num) {
            return true;
        }
        if ($sqrt > $num) {
            $right = $mid - 1;
        } else {
            $left = $mid + 1;
        }
    }
    return false;
}